package 代码记录.指定公司代码练习记录.华为_2024.分值200;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author zx
 * @create 2024-02-16 14:42
 * 类似于 - 分割等和子集_416 - (01背包)
 */
public class MELON的难题_6 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();

        String input = sc.nextLine();
        List<Integer> nums = split(input);

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 2 != 0) {
            System.out.println(-1);
            return;
        }

        int target = sum / 2;
        int result = findMinCount(nums, n, target);

        if (result == n) {
            System.out.println(-1);
        } else {
            // 输出最优解
            System.out.println(result);
        }
    }

    private static List<Integer> split(String paramsStr) {
        String[] tokens = paramsStr.split(" ");
        List<Integer> result = new ArrayList<>();
        for (String token : tokens) {
            result.add(Integer.parseInt(token));
        }
        return result;
    }

    private static int findMinCount(List<Integer> nums, int n, int target) {
        int[][] dp = new int[n + 1][target + 1];

        for (int i = 0; i <= target; i++) {
            dp[0][i] = n;
        }

        for (int i = 1; i <= n; i++) {
            int num = nums.get(i - 1);
            for (int j = 1; j <= target; j++) {
                if (j < num) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - num] + 1);
                }
            }
        }

        return dp[n][target];
    }
}
